// Copyright (c) [2019] [huazhonghua]
// [理解] is licensed under the Mulan PSL v1.
// You can use this software according to the terms and conditions of the Mulan PSL v1.
// You may obtain a copy of Mulan PSL v1 at:
//     http://license.coscl.org.cn/MulanPSL
// THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND, EITHER EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR
// PURPOSE.
// See the Mulan PSL v1 for more details.

#include <stdio.h>
#include <time.h>

int fibonacci(int n) {
	if(n < 0) return -1;
	if(n == 0) return 0;
	if(n == 1) return 1;
	int fib1 = fibonacci(n - 1);
	int fib2 = fibonacci(n - 2);
	return fib1 + fib2;
}

int main() {

	clock_t begin = clock();

	int n = 15;
	int last = 1;
	int last_last = 0;

	for(int i = 2; i <= n; ++i) {
		int fib = last + last_last;
		last_last = last;
		last = fib;
	}

	clock_t end = clock();
	double time_used = (double)(end - begin) / CLOCKS_PER_SEC;

	printf("%d time %f\n", last, time_used);


	begin = clock();

	int result = fibonacci(n);

	end = clock();
	time_used = (double)(end - begin) / CLOCKS_PER_SEC;

	printf("%d time %f\n", result, time_used);


	return 0;
}
